package LeetCode;

import java.util.*;

public class LC_347_TopKFrequentElements {

    public static void main(String[] args) {

    }

    class Pair {
        int num;
        int count;

        Pair(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }

    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int num : nums)
                if (map.containsKey(num)) map.put(num, map.get(num) + 1);
                else map.put(num, 1);

            PriorityQueue<Pair> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.count));
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                Pair p = new Pair(entry.getKey(), entry.getValue());
                queue.offer(p);
                if (queue.size() > k) queue.poll();
            }

            List<Integer> result = new ArrayList<>();
            while (queue.size() > 0) result.add(queue.poll().num);
            Collections.reverse(result);
            return result;
        }
    }


    static class Solution_2 {

        public List<Integer> topKFrequent(int[] nums, int k) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                if (map.containsKey(num)) map.put(num, map.get(num) + 1);
                else map.put(num, 1);
            }

            int max = 0;
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) max = Math.max(max, entry.getValue());

            ArrayList<Integer>[] arr = (ArrayList<Integer>[]) new ArrayList[max + 1];
            for (int i = 1; i <= max; i++) arr[i] = new ArrayList<>();

            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int count = entry.getValue();
                int number = entry.getKey();
                arr[count].add(number);
            }

            List<Integer> result = new ArrayList<>();
            for (int j = max; j >= 1; j--) {
                if (arr[j].size() > 0) for (int a : arr[j]) result.add(a);
                if (result.size() == k)
                    break;
            }
            return result;
        }

    }


    public class Solution_3 {
        public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer> result = new ArrayList<Integer>();
            HashMap<Integer, Integer> counter = new HashMap<>();
            for (int i : nums)
                if (counter.containsKey(i)) counter.put(i, counter.get(i) + 1);
                else counter.put(i, 1);
            TreeMap<Integer, Integer> sortedMap = new TreeMap<>(new ValueComparator(counter));
            sortedMap.putAll(counter);

            int i = 0;
            for (Map.Entry<Integer, Integer> entry : sortedMap.entrySet()) {
                result.add(entry.getKey());
                i++;
                if (i == k) break;
            }

            return result;
        }
    }

    class ValueComparator implements Comparator<Integer> {
        HashMap<Integer, Integer> map = new HashMap<>();

        ValueComparator(HashMap<Integer, Integer> m) {
            map.putAll(m);
        }

        public int compare(Integer i1, Integer i2) {
            int diff = map.get(i2) - map.get(i1);
            if (diff == 0) return 1;
            else return diff;
        }
    }

}